package com.zhugang.week08;

import java.util.*;

/**
 * @program algorithms
 * @description: combinationSumDup
 * @author: chanzhugang
 * @create: 2022/08/19 15:48
 */
public class CombinationSumDup {

    /**
     * 40 组合总和 II
     *
     * @param candidates
     * @param target
     * @return
     */
    private List<List<Integer>> result = new ArrayList<>();

    public List<List<Integer>> combinationSumDup(int[] candidates, int target) {
        // 数组中有重复元素， 每个元素只能试用一次
        /**
         * 统计元素出现的个数，放在两个对应的数组中
         */
        Map<Integer, Integer> countMap = new HashMap<>();
        for (int i = 0; i < candidates.length; i++) {
            int count = 1;
            if (countMap.containsKey(candidates[i])) {
                count += countMap.get(candidates[i]);
            }
            countMap.put(candidates[i], count);
        }
        List<Integer> nums = new ArrayList<>();
        List<Integer> counts = new ArrayList<>();
        for (int i = 0; i < candidates.length; i++) {
            if (countMap.containsKey(candidates[i])) {
                nums.add(candidates[i]);
                counts.add(countMap.get(candidates[i]));
                // 移除map中元素
                countMap.remove(candidates[i]);
            }
        }

        backtrack(nums, counts, 0, target, new ArrayList<>());
        return result;
    }

    /**
     * @param nums   元素
     * @param counts 频次
     * @param k      阶段
     * @param left   剩余值
     * @param path   路径
     */
    private void backtrack(List<Integer> nums, List<Integer> counts, int k, int left, List<Integer> path) {
        if (left == 0) {
            result.add(new ArrayList<>(path));
            return;
        }
        if (left < 0 || k == nums.size()) {
            return;
        }

        for (int count = 0; count <= counts.get(k); count++) {
            for (int i = 0; i < count; i++) {
                // 每个元素出现的次数
                path.add(nums.get(k));
            }

            backtrack(nums, counts, k + 1, left - count * nums.get(k), path);
            for (int i = 0; i < count; i++) {
                path.remove(path.size() - 1);
            }
        }
    }
}